package other.sort;

import common.util.MyUtil;

/**
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(1)
 *
 * @author guichang
 * @date 2020/9/24
 */

public class P4_快速排序 {

    public static void main(String[] args) {

        int[] nums = MyUtil.createRandomArray(10, 1, 99);
        quickSort(nums, 0, nums.length - 1);

        MyUtil.printInt(nums);
    }

    private static void quickSort(int[] nums, int left, int right) {
        // 只有一个不用排了
        if (left >= right) {
            return;
        }
        // 排序并返回基准点，左边的数都比基准点小，右边的都比基准点大
        int mid = partition(nums, left, right);
        // 递归处理左边
        quickSort(nums, left, mid - 1);
        // 递归处理右边
        quickSort(nums, mid + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        // 基准值取最后一个
        int baseValue = nums[right];
        while (left < right) {
            // 从左往右找到第一个比基准值大的索引
            while (left < right && nums[left] <= baseValue) {
                left++;
            }
            // 交换
            MyUtil.swap(nums, left, right);

            // 从右往左找到第一个比基准值小的索引
            while (left < right && nums[right] >= baseValue) {
                right--;
            }
            // 交换
            MyUtil.swap(nums, left, right);
        }
        // 到这就是left==right，随便取一个
        return left;
    }

}